package stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
将中缀表达式转为后缀表达式
1) 初始化两个栈：运算符栈s1和储存中间结果的栈s2；s2可以用集合来替代
2) 从左至右扫描中缀表达式；
3) 遇到操作数时，将其压s2；
4) 遇到运算符时，比较其与s1栈顶运算符的优先级：
1.如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
2.否则，若优先级比栈顶运算符的高，也将运算符压入s1；
3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
5) 遇到括号时：(1) 如果是左括号“(”，则直接压入s1
(2) 如果是右括号“)”，
则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6) 重复步骤2至5，直到表达式的最右边
7) 将s1中剩余的运算符依次弹出并压入s2
8) 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
    (s2用集合来代替，就不用逆序了)
* */
public class PolandNotation {
    public static void main(String[] args) {
        String expression = "111+((22+3)*44)-51";
        List<String> exList = Calculator.expressionToList(expression);
        System.out.println(exList);
        Stack<String> s1 = new Stack<>();
        List<String> s2 = new ArrayList<>();
        for (String s : exList) {
            if(s.matches("\\d+")) {
                s2.add(s);
            }else if(s.equals("(")) {
                s1.push(s);
            }else if(s.equals(")")) {
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();
            }else {
                while (true) {
                    if(s1.isEmpty() || "(".equals(s1.peek()) ||
                            priority(s) > priority(s1.peek())) {
                        s1.push(s);
                        break;
                    }else {
                        s2.add(s1.pop());
                    }
                }
            }
        }
        while (!s1.isEmpty()) {
            s2.add(s1.pop());
        }
        System.out.println(s2);//得到了后缀表达式
        /*后缀表达式的计算机求值
        从左至右扫描表达式，遇到数字时，将数字压入栈中，遇到运算符时，
        弹出栈顶的两个数，用运算符对他们做相应的计算，并将结果入栈，重复
        上述过程知道表达式最右端，最后运算得出的值即为表达式的结果
        * */
        for (String s :s2) {
            if(s.matches("\\d+")) {
                s1.push(s);
            }else {
                String num1 = s1.pop();
                String num2 = s1.pop();
                s1.push(
                Calculator.operation(Integer.parseInt(num1),Integer.parseInt(num2),s.charAt(0))+""
                );
            }
        }
        System.out.println("运算结果:"+s1.pop());
    }
    public static int priority(String str) {
        if("*".equals(str) || "/".equals(str)) {
            return 1;
        }else if("+".equals(str) || "-".equals(str)) {
            return 0;
        }else {
            throw new RuntimeException("运算符有误");
        }
    }
}
